package algorithms;

/**
 * @功能
 * @创建时间 2020/6/6
 */
public class BinarySearch {
    public static int search(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int middle = (start + end) / 2;
            if (key < arr[middle]) {
                end = middle - 1;
            } else if (key > arr[middle]) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
    public static int rank(int[] arr, int key){
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int middle = (start + end) / 2;
            if (key < arr[middle]) {
                end = middle - 1;
            } else if (key > arr[middle]) {
                start = middle + 1;
            } else {
                while (key == arr[middle])
                    middle--;
                return middle;
            }
        }
        return -1;

    }
    public static int count(int[] arr, int key){
        int start = 0;
        int end = arr.length - 1;
        int count =0;
        int tmp=0;
        while (start <= end) {
            int middle = (start + end) / 2;
            if (key < arr[middle]) {
                end = middle - 1;
            } else if (key > arr[middle]) {
                start = middle + 1;
            } else {
                tmp=middle;
                while (key == arr[middle])
                {    middle--;
                count++;}
                while (key == arr[tmp+1])
                {    tmp++;
                    count++;}
                return count;
            }
        }
        return -1;

    }
}
